package A一周刷爆LeetCode.A基础班.I暴力递归;

/**
 * @author wei.zhao
 * @description: 拿纸牌第二种解法
 * @date 2022/12/6 11:21
 */
public class Code07_CardsInLine_02 {

    public static void main(String[] args) {
        int[] arr = {1, 2, 100, 4,9,26,6,7,100,67,89,12435,78,65,88888,6574,112,654,77777};
        System.out.println(f(arr, 0, arr.length - 1));
        System.out.println(Math.min(f(arr, 0, arr.length - 2), f(arr, 1, arr.length - 1)));
    }

    public static int f(int[] arr, int l, int r) {
        // 只剩一个，没有后手了，直接拿走
        if (l == r) {
            return arr[l];
        }
        // 只剩两个，也没有后手了，直接拿走较大的
        if (l +1 == r) {
            return Math.max(arr[l],arr[r]);
        }
        // 超过两个，拿走左边的或者右边的，剩下的递归
        int chooseL = arr[l] + Math.min(f(arr, l + 2, r), f(arr, l+1, r - 1));
        int chooseR = arr[r] + Math.min(f(arr, l, r - 2), f(arr, l + 1, r-1));
        return Math.max(chooseL, chooseR);
    }

}
